package com.heima.leetcode.datastructure.hashtable;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * 将字母异位词分组
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/26 10:47
 */
public class GroupAnagrams {

    /**
     * <h3>方法一：hashMap</h3>
     * 思路：
     * <p>将字母异位词排序的结果作为key，当前异位词加入到List<异位词>中作为值，存入哈希表中</p>
     * <p>如果哈希表中有当前对应的key，则改变值，也就是List集合继续加入当前词</p>
     * <P>返回哈希表的值构成的集合</P>
     * @param strArray 字符串数组
     * @return 分组结果
     */
    public static List<List<String>> groupAnagrams1(String[] strArray) {
        HashMap<String, List<String>> hashMap = new HashMap<>();
        for (String s : strArray) {
            char[] charArray = s.toCharArray();
            Arrays.sort(charArray);
            String key = new String(charArray);
            List<String> list = hashMap.computeIfAbsent(key, k -> new ArrayList<>());
            list.add(s);
        }
        return new ArrayList<>(hashMap.values());
    }

    /**
     * 数组作为键
     */
    static class ArrayKey{
        private final int[] array = new int[26];

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ArrayKey arrayKey = (ArrayKey) o;
            return Arrays.equals(array, arrayKey.array);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(array);
        }

        ArrayKey(String str) {
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                array[c - 'a']++;
            }
        }
    }

    /**
     * <h3>方法二：用长度26的数组作为哈希表的key</h3>
     * @param strArray 字符串数组
     * @return 返回分组结果
     */
    public static List<List<String>> groupAnagrams2(String[] strArray){
        HashMap<ArrayKey, List<String>> hashMap = new HashMap<>();
        for (String s : strArray) {
            ArrayKey arrayKey = new ArrayKey(s);
            List<String> list = hashMap.computeIfAbsent(arrayKey, k -> new ArrayList<>());
            list.add(s);
        }
        return new ArrayList<>(hashMap.values());
    }
}
